package com.linyaonan.leetcode.medium._875;

import java.util.Arrays;

/**
 *
 * 珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
 *
 * 珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
 *
 * 珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
 *
 * 返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
 *
 *
 *
 * 示例 1：
 *
 * 输入：piles = [3,6,7,11], h = 8
 * 输出：4
 * 示例 2：
 *
 * 输入：piles = [30,11,23,4,20], h = 5
 * 输出：30
 * 示例 3：
 *
 * 输入：piles = [30,11,23,4,20], h = 6
 * 输出：23
 *
 *
 * 提示：
 *
 * 1 <= piles.length <= 10^4
 * piles.length <= h <= 10^9
 * 1 <= piles[i] <= 10^9
 *
 * @author: Lin
 * @date: 2024/2/22
 */
public class KokoEatingBananas {

    public long getTime(int[] piles, int speed) {
        // 防止数值溢出
        long time = 0;
        for (int pile : piles) {
            int curTime = (pile + speed - 1) / speed;
            time += curTime;
        }
        return time;
    }

    public int minEatingSpeed(int[] piles, int h) {
        // 1. 考虑边界
        if (piles.length == h) {
            // 找出最大的数值返回即可
            Arrays.sort(piles);
            return piles[piles.length - 1];
        }

        // 2. 香蕉数 / k 向上取整后得到的为一堆香蕉吃完的时间
        // 边界为吃1根到吃max跟
        int low = 1;
        int high = 0;
        for (int pile : piles) {
            high = Math.max(high, pile);
        }
        int k = high;
        while (low < high) {
            int speed = (high + low) >>> 1;
            long time = getTime(piles, speed);
            if (time <= h) {
                k = speed;
                high = speed;
            } else {
                low = speed + 1;
            }
        }
        return k;
    }

    /**
     * 通过升序数组，找到每次吃eat根需要多少次
     * @param piles
     * @param eat
     * @return
     */
    public int getCount(int[] piles, int eat) {
        int max = piles[piles.length - 1];

        int count = (int) Math.ceil((double) max / eat);

        int result = 0;
        int preIndex = -1;
        // 以3,6,7,11为例，eat=4
        // 1,2,2,3
        for (int i = 1; i <= count; i++) {
            int t = i * eat;
            int index = getleftIndex(piles, t);
            result += Math.max((index - preIndex), 0) * i;
            preIndex = index;
        }
        return result;
    }

    /**
     * 从升序数组中，找到小于等于目标值的最大索引
     * @param piles
     * @param t
     * @return
     */
    public int getleftIndex(int[] piles, int t) {
        int l = 0;
        int r = piles.length - 1;

        int index = -1;

        while (l <= r) {
            int m = (l + r) >>> 1;
            int numM = piles[m];
            if (numM == t) {
                index = m;
                r = m - 1;

            } else if (numM < t) {
                if (m < index) {
                    break;
                }

                index = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }

        return index;
    }


    /**
     * 二分查找，left=1，right = sum(piles)
     * @param piles
     * @param h
     * @return
     */
    public int minEatingSpeed2(int[] piles, int h) {
        long add = 0L;
        for (int pile : piles) {
            add += pile;
        }

        long l = 1L;
        long r = add;

        long rr = add;

        while (l <= r) {
            long m = l + (r - l) / 2;
            long temp = time(piles, m);
            if (temp <= h) {
                rr = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        return (int) rr;

    }

    public long time(int[] piles, long speed) {
        long result = 0L;
        for (int pile : piles) {
            // 向上取整
            result += (pile + speed - 1) / speed;
        }
        return result;
    }

}
